package cn.com.mdx.collection.queue;

import edu.princeton.cs.algs4.StdRandom;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * <p> 随机队列
 *
 * @author ：huangy
 * @date ：Created in 2020/8/18 9:59 下午
 */
@SuppressWarnings("unchecked")
public class RandomQueue<Item> implements Iterable<Item> {

    /**
     * 初始容量
     */
    private final static int DEFAULT_CAPACITY = 10;

    /**
     * 队列容量
     */
    private int size;

    private Item[] items;

    public RandomQueue() {
        this.size = 0;
        this.items = (Item[]) new Object[DEFAULT_CAPACITY];
    }

    /**
     * @param item 入队列元素
     * @Author huangy
     * @description //TODO 元素入队列
     * @date 10:07 下午 2020/8/18
     **/
    public void enqueue(Item item) {
        if (size + 1 == items.length) resize(items.length * 2);
        items[size++] = item;
    }

    /**
     * @return Item 出队列元素
     * @Author huangy
     * @description //TODO 元素出队列
     * @date 10:09 下午 2020/8/18
     **/
    public Item dequeue() {
        if (isEmpty()) throw new UnsupportedOperationException("队列为空");
        if(size - 1 == items.length / 4) resize(items.length / 2);
        //随机一个数来作为出队列的元素位置
        int randomNum = StdRandom.uniform(size);
        Item item = items[randomNum];
        items[randomNum] = items[--size];
        return item;
    }

    /**
     * @return int 队列容量
     * @Author huangy
     * @description //TODO 获取队列容量
     * @date 10:09 下午 2020/8/18
     **/
    public int size() {
        return size;
    }

    /**
     * @return boolean true 空 false 非空
     * @Author huangy
     * @description //TODO 判断队列是否为空
     * @date 10:10 下午 2020/8/18
     **/
    public boolean isEmpty() {
        return size == 0;
    }

    private void resize(int itemsLength) {
        assert itemsLength < size;
        Item[] newArray = (Item[]) new Object[itemsLength];
        if (size >= 0) System.arraycopy(items, 0, newArray, 0, size);
        items = newArray;
    }

    private class RandomQueueIterator implements Iterator<Item> {
        private final Item[] itemsCopy = (Item[]) new Object[size];
        private int sizeCopy = size;

        public RandomQueueIterator() {
            if (size >= 0) {
                System.arraycopy(items, 0, itemsCopy, 0, size);
            }
        }

        @Override
        public boolean hasNext() {
            return sizeCopy > 0;
        }

        @Override
        public Item next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            int randomNum = StdRandom.uniform(sizeCopy);
            Item item = itemsCopy[randomNum];
            if (randomNum != --sizeCopy) {
                itemsCopy[randomNum] = itemsCopy[sizeCopy];
            }
            itemsCopy[sizeCopy] = null;
            return item;
        }
    }

    @Override
    public Iterator<Item> iterator() {
        return new RandomQueueIterator();
    }

    public static void main(String[] args) {
        RandomQueue<Integer> randomQueue = new RandomQueue<>();
        for (int i = 0; i < 50; i++) {
            randomQueue.enqueue(i);
        }
        for(int i: randomQueue) System.out.println(i);
        for (int i = 0; i < 50; i++) {
            System.out.println(randomQueue.dequeue());
        }
    }

}
